Search results for "Theoretical computer science"

Abstracts from the CECAM workshop on computer simulations of cellular automata

1989

Efficient generation of restricted growth words

2013

A length n restricted growth word is a word w=w"1w"2...w"n over the set of integers where w"1=0 and each w"i, i>1, lies between 0 and the value of a word statistics of the prefix w"1w"2...w"i"-"1 of w, plus one. Restricted growth words simultaneously generalize combinatorial objects as restricted growth functions, staircase words and ascent or binary sequences. Here we give a generic generating algorithm for restricted growth words. It produces a Gray code and runs in constant average time provided that the corresponding statistics has some local properties.

Restricted compositions and permutations: from old to new Gray codes

2011

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let @? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of @? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that @? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval si…

Statistics-preserving bijections between classical and cyclic permutations

2012

Recently, Elizalde (2011) [2] has presented a bijection between the set C"n"+"1 of cyclic permutations on {1,2,...,n+1} and the set of permutations on {1,2,...,n} that preserves the descent set of the first n entries and the set of weak excedances. In this paper, we construct a bijection from C"n"+"1 to S"n that preserves the weak excedance set and that transfers quasi-fixed points into fixed points and left-to-right maxima into themselves. This induces a bijection from the set D"n of derangements to the set C"n"+"1^q of cycles without quasi-fixed points that preserves the weak excedance set. Moreover, we exhibit a kind of discrete continuity between C"n"+"1 and S"n that preserves at each s…

Coupling agent-based with equation-based models to study spatially explicit megapopulation dynamics

2018

International audience; The incorporation of the spatial heterogeneity of real landscapes into population dynamics remains extremely difficult. We propose combining equation-based modelling (EBM) and agent-based modelling (ABM) to overcome the difficulties classically encountered. ABM facilitates the description of entities that act according to specific rules evolving on various scales. However, a large number of entities may lead to computational difficulties (e.g., for populations of small mammals, such as voles, that can exceed millions of individuals). Here, EBM handles age-structured population growth, and ABM represents the spreading of voles on large scales. Simulations applied to t…

Null models for animal social network analysis and data collected via focal sampling: Pre‐network or node network permutation?

2020

In social networks analysis, two different approaches have predominated in creating null models for hypothesis testing, namely pre‐network and node network permutation approaches. Although the pre‐network permutation approach appears more advantageous, its use has mainly been restricted to data on associations and sampling methods such as ‘group follows’. The pre‐network permutation approach has recently been adapted to data on interactions and the focal sampling method, but its performance in different scenarios has not been thoroughly explored. Here, we assessed the performance of the pre‐network and node network permutation approach in several simulated scenarios based on proneness to fa…

Bit-parallel approximate pattern matching: Kepler GPU versus Xeon Phi

2016

Advanced SIMD features on GPUs and Xeon Phis promote efficient long pattern search.A tiled approach to accelerating the Wu-Manber algorithm on GPUs has been proposed.Both the GPU and Xeon Phi yield two orders-of-magnitude speedup over one CPU core.The GPU-based version with tiling runs up to 2.9 × faster than the Xeon Phi version. Approximate pattern matching (APM) targets to find the occurrences of a pattern inside a subject text allowing a limited number of errors. It has been widely used in many application areas such as bioinformatics and information retrieval. Bit-parallel APM takes advantage of the intrinsic parallelism of bitwise operations inside a machine word. This approach typica…

Usability and acceptability assessment of an empathic virtual agent to prevent major depression

2016

In Human-Computer Interaction, the adaptation of the content and the way of how this content is communicated to the users in interactive sessions is a critical issue to promote the acceptability and usability of any computational system. We present a user-adapted interactive platform to identify and provide an early intervention for symptoms of depression and suicide. In particular, we describe the work performed to assess users' system acceptability and usability. An empathic Virtual Agent is the main interface with the user, and it has been designed to generate the appropriate dialogues and emotions during the interactions according to the detected user's specific needs. This personalizat…

Robust Network Agreement on Logical Information

2011

Abstract Logical consensus is an approach to distributed decision making which is based on the availability of a network of agents with incomplete system knowledge. The method requires the construction of a Boolean map which defines a dynamic system allowing the entire network to consent on a unique, global decision. Previous work by the authors proved the method to be viable for applications such as intrusion detection within a structured environment, when the agent's communication topology is known in advance. The current work aims at providing a fully distributed protocol, requiring no a priori knowledge of each agent's communication neighbors. The protocol allows the construction of a r…

Large multiple neighborhood search for the soft-clustered vehicle-routing problem

2021

Abstract The soft-clustered vehicle-routing problem (SoftCluVRP) is a variant of the classical capacitated vehicle-routing problem. Customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. In this paper, we present a large multiple neighborhood search for the SoftCluVRP. We design and analyze multiple cluster destroy and repair operators as well as two post-optimization components, which are both based on variable neighborhood descent. The first allows inter-route exchanges of complete clusters, while the second searches for intra-route improvements by combining classical neighborhoods (2-opt, Or-opt, double-bridge) and the Balas-Simo…